package leetcode_500;

import java.util.Arrays;

/**
 *@author 周杨
 *PartitionEqualSubsetSum_416 判断一个数组是否能划分为两个值相等的子数组(顺序可以打乱)
 *describe:由于用例明确限定输入大小 所以用dp数组保存已知结果 AC 88%
 *2018年7月23日 下午2:35:56
 */
public class PartitionEqualSubsetSum_416 {
	
	public static void main(String[] args) {
		PartitionEqualSubsetSum_416 test=new PartitionEqualSubsetSum_416();
		//System.out.println(test.canPartition(new int[] {3,3,3,4,5}));
		System.out.println(test.canPartition(new int[] {100,100,100,100,100,100,100,100}));
	}
	
	 /**
	 * describe:排序后划分区域 思想错误
	 * 2018年7月23日 下午2:39:15
	 */
	public boolean canPartition1(int[] nums) {
		 Arrays.sort(nums);
		 int count=0;
		 for(int i:nums)
			 count+=i;
		 if(count%2!=0)
			 return false;
		 count/=2;
		 int now=0;
		 for(int i:nums) {
			 now+=i;
			 if(now==count)
				 return true;
			 if(now>count)
				 return false;
		 }
		 return false;
	 }
	
	/**
	 * describe:动态规划 此方法仅适合num里面每个数并不大的情况
	 * 2018年7月23日 下午8:37:09
	 */
	public boolean canPartition(int[] nums) {
		int count=0;
		 for(int i:nums)
			 count+=i;
		 if(count%2==1)
			 return false;
		 count/=2;
		 boolean dp[]=new boolean[count+1];
		 dp[0]=true;
		 int nowMax=0;
		 for(int i:nums) {
			 if(i>count)
				 return false;
			 if(dp[count-i])
				 return true;
			 for(int j=nowMax;j>=0;--j) {
				 if(dp[j]&&j+i<count) {
					 dp[j+i]=true;
					 nowMax=Math.max(i+j, nowMax);
				 }
			 }
		 }
		 return false;
	 }
}
